package JZOffer;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

// 队列的最大值
public class JzOffer59II {
    private Queue<Integer> queue;
    private Deque<Integer> maxQueue;

    public JzOffer59II() {
        queue = new LinkedList<>();
        maxQueue = new LinkedList<>();
    }

    public int max_value() {
        return maxQueue.isEmpty() ? -1 : maxQueue.peekFirst();
    }

    public void push_back(int value) {
        queue.add(value);
        while (!maxQueue.isEmpty() && maxQueue.peekLast() < value) {
            maxQueue.pollLast();
        }
        maxQueue.offerLast(value);
    }

    public int pop_front() {
        if (queue.isEmpty()) {
            return -1;
        }
        int x = queue.poll();
        if (maxQueue.peekFirst() == x) {
            maxQueue.pollFirst();
        }
        return x;
    }

    public static void main(String[] args) {
        JzOffer59II jzOffer59II = new JzOffer59II();

        jzOffer59II.push_back(1);
        jzOffer59II.push_back(2);
        System.out.println(jzOffer59II.max_value());
    }
}
